Resilient transmission of digital information is an important problem and much development has been done in this area. A general description of the problem is how to move data from a source to a destination, separated by a channel across a distance and/or a time, resiliently, i.e., in a manner that allows for recovery of errors that the channel may introduce in the data as it moves.
Forward error correction (“FEC”) provides a mechanism for error detection/correction. An FEC encoder encodes the data to be sent into a form that contains, in addition to the original information of the data, redundant data that may help in recovering the original data if it is corrupted by the channel. In a typical case, but not always, the data to be transmitted is representable as a set of bit values, or vectors of bit values, called symbols. With FEC, redundant symbols are calculated from the input symbols and the input symbols and redundant symbols are what are sent through the channel. In a variation, the original input symbols are not explicitly present but can be recovered from what is sent. That variation is referred to as “nonsystematic” encoding.
There are a variety of communications channels to which the method of forward error correction can be used. A communications channel could be one in which transmission is carried over space, between two spatially separated users, such as, for example, transmission of voice across a wireless telephone network or transmission of TV signals between a transmitter and a sender via a satellite. Corruption of data can occur for a variety of physical reasons, such as atmospheric discharges, rain attenuation, or simply obstacles in the transmission path used by the channel.
A communications channel could also facilitate transmission over time. Such is the case for storage media for example, where data is stored at one time and read from the same device at a different time. In this case, corruption can occur, for example, when scratches on the surface of the physical storage device lead to errors of the read head. In general, where the device uses magnetization of the surface to store information, the strength of such magnetization may fade for a variety of reasons, leading to an inaccurate measurement of the stored data, and ultimately to read errors. If unprotected, such errors cause a catastrophic loss of information, rendering storage of digital information largely ineffective.
However the errors occur, FEC can be used to recover from those errors. One particular type of FEC often employed in communication using Reed-Solomon coding. Reed-Solomon coding is well known. See, for example, Lin, S., and Costello, D., “Error Control Coding Fundamentals and Applications” or MacWilliams, F. J., and Sloane, N., “The Theory of Error-Correcting Codes”. Reed-Solomon codes have a desirable advantage in that they can guarantee recovery from some maximum number of errors determined by the number of original symbols forming a block and the number of redundant symbols for that block. A data transmission error is any event that changes the value or apparent value of a symbol to something other than its original value.
Specifically, where a Reed-Solomon encoder encodes k input symbols with r redundant symbols and the sender transmits those n=k+r encoded symbols, a Reed-Solomon decoder is capable of correcting any pattern of r/2 errors in the received n symbols, regardless of their magnitude or their position. However, while larger values of k and r allow for greater numbers of errors, the computational effort rises nonlinearly and thus poses limits of their size.
The symbol-based mode of operation of Reed-Solomon codes makes it an ideal choice in situations where the underlying bits of information are corrupted in bursts, rather than randomly, leading to a smaller number of symbol errors. Encoding and decoding of data using Reed-Solomon codes over an alphabet of size q requires various arithmetic operations with polynomials over the field GF(q) with q elements. Typically, the code is specified by a set of “roots” which are n=k+r consecutive powers of a primitive element α of the underlying field. Often in practice these roots are just the first n powers of α, starting from the power 1=α0, but this need not always be the case.
An encoding operation might start with calculating a polynomial g(x) of degree r, called the generator polynomial of the code. This polynomial is obtained as the polynomial of smallest degree having the first r consecutive powers of a (starting with 1=α0) as its roots. Next, the vector inp(0), . . . , inp(k−1) of input symbols is represented as the polynomial xr*(inp(0)+inp(1)*x+ . . . +inp(k−1)*xk-1), and this polynomial is in turn divided by the generator polynomial g(x). The coefficients of the remainder of this division, which is a polynomial of degree less than r, are interpreted as the r redundant symbols corresponding to the input symbols.
The division by g(x) is typically accomplished in hardware using a device called a linear feedback shift register, which can be faster than doing this in software. Such a device has the advantage of being simple to implement in hardware, and not requiring the entire input sequence be present at the onset of the decoding. In contrast, at every computation cycle, one more input symbol needs to be injected into the decoder, leading to a pipelined encoding architecture.
In a typical approach, the decoding of Reed-Solomon codes is accomplished in several steps upon reception of a (possibly corrupted) word y(0), . . . , y(n−1): (i) calculation of the syndromes, (ii) calculation of the error-locator and error-value polynomials, (iii) performing a Chien search to recover the roots of the error-locator, and with that the error positions, and (iv) calculating the error values. Such operations can be done in hardware, software or a combination that might involve dedicated hardware and/or software elements.
In a first step, r syndromes s(0), . . . , s(r−1) are calculated from the received symbols y(0), . . . , y(n−1). Next, the syndromes are forwarded to a unit/module/etc. that calculates two polynomials, v(x) and u(x), where u(x) is of degree t, t being the actual number of errors in the received word, and v(x) is of degree smaller than t. These two polynomials are often computed by hardware and/or software using the Berlekamp-Massey algorithm. The roots of the polynomial u(x) among the first n powers of a determine the positions of the errors. These roots can be calculated with a procedure that is very efficient for hardware implementation called the “Chien search” procedure. In a Chien search, all consecutive powers of α are tried, one-by-one, and whenever a root of the polynomial u(x) is found, a corresponding error position is noted and saved. Finally, using Fomey's formulas or other method, the error values are calculated from u(x) and the error value polynomial v(x).
The need for ever more powerful applications requires the transmission of larger and larger pieces of data. With this comes the need for protection of larger pieces of data. Current methods for encoding and decoding of data using Reed-Solomon codes will require more resources on the digital processors or electronic circuits that are used to perform these methods. Often, these processors are meant for tasks that are more relevant to the application than encoding and decoding. For example, when a movie is to be shown on a wireless device, most of the processing time is spent on the processing the movie (e.g., decompression and rendering for the display) than on communication of the bits representing the movie.
The situation is even more pronounced for storage devices where block sizes are increasing and encoding results in better protection of the data, and ultimately a better commercial advantage against other storage technologies. More concretely, in a typical storage application, data is read units of “sectors”. The size of a sector is measured in bytes, and is typically in the range of 512 through 1024 bytes, though it is expected that new sector sizes grow to 4096 bytes as storage devices increase in overall capacity. In the upper range of this interval, that is, when the sector size is 4096, it could be advisable to work with a Reed-Solomon code over the field GF(4096), in which the value of k is 2731, corresponding to roughly 4096 bytes. In this case, the Chien search comprises looking through 2731 powers of the element α. This rather large number could lead to computational bottlenecks.
What is desired is a different method of encoding data that has the desirable error-correction advantages of Reed-Solomon codes, but also allows for faster decoding without requiring significant increases in hardware costs.